package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/27 上午10:24
 */
public class 恢复二叉搜索树 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);

        TreeNode left = new TreeNode(3);

        root.left = left;

        left.right = new TreeNode(2);

        recoverTree(root);

        System.out.println();


    }

    public static void recoverTree(TreeNode root) {
        List<TreeNode> l = new ArrayList<>();
        TreeNode[] tl = new TreeNode[l.size()];
        bst(l,root);
        tl = l.toArray(tl);
        for(int i = 0;i < tl.length;i++){
            TreeNode pre = tl[i];
            int li = 2 * i + 1;
            int ri = 2 * i + 2;
            if(li < tl.length && tl[li] != null && tl[li].val > pre.val){
                swap(tl[li],pre);
            }
            if(ri < tl.length && tl[ri] != null && tl[ri].val < pre.val){
                swap(tl[ri],pre);
            }
        }
    }

    public static void bst(List<TreeNode> l, TreeNode node){
        if (node == null){
            return;
        }
        if (node.left == null && node.right == null){
            return;
        }

        l.add(node);
        if(node.left != null) {
            bst(l, node.left);
        }else{
            l.add(null);
        }
        if(node.left != null) {
            bst(l, node.right);
        }else{
            l.add(null);
        }
    }

    public static void swap(TreeNode a,TreeNode b){
        int t = b.val;
        b.val = a.val;
        a.val = t;
    }

    
    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

}
